{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Pairs of Strings With Concatenation Equal to Target"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numOfPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连接后等于目标字符串的字符串对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>数字</strong>&nbsp;字符串数组 <code>nums</code>&nbsp;和一个 <strong>数字</strong>&nbsp;字符串 <code>target</code>&nbsp;，请你返回 <code>nums[i] + nums[j]</code>&nbsp;（两个字符串连接）结果等于 <code>target</code>&nbsp;的下标 <code>(i, j)</code>&nbsp;（需满足 <code>i != j</code>）的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [\"777\",\"7\",\"77\",\"77\"], target = \"7777\"\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>符合要求的下标对包括：\n",
    "- (0, 1)：\"777\" + \"7\"\n",
    "- (1, 0)：\"7\" + \"777\"\n",
    "- (2, 3)：\"77\" + \"77\"\n",
    "- (3, 2)：\"77\" + \"77\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [\"123\",\"4\",\"12\",\"34\"], target = \"1234\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>符合要求的下标对包括\n",
    "- (0, 1)：\"123\" + \"4\"\n",
    "- (2, 3)：\"12\" + \"34\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [\"1\",\"1\",\"1\"], target = \"11\"\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>符合要求的下标对包括\n",
    "- (0, 1)：\"1\" + \"1\"\n",
    "- (1, 0)：\"1\" + \"1\"\n",
    "- (0, 2)：\"1\" + \"1\"\n",
    "- (2, 0)：\"1\" + \"1\"\n",
    "- (1, 2)：\"1\" + \"1\"\n",
    "- (2, 1)：\"1\" + \"1\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i].length &lt;= 100</code></li>\n",
    "\t<li><code>2 &lt;= target.length &lt;= 100</code></li>\n",
    "\t<li><code>nums[i]</code>&nbsp;和&nbsp;<code>target</code>&nbsp;只包含数字。</li>\n",
    "\t<li><code>nums[i]</code>&nbsp;和&nbsp;<code>target</code>&nbsp;不含有任何前导 0 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-pairs-of-strings-with-concatenation-equal-to-target](https://leetcode.cn/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-pairs-of-strings-with-concatenation-equal-to-target](https://leetcode.cn/problems/number-of-pairs-of-strings-with-concatenation-equal-to-target/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"777\",\"7\",\"77\",\"77\"]\\n\"7777\"', '[\"123\",\"4\",\"12\",\"34\"]\\n\"1234\"', '[\"1\",\"1\",\"1\"]\\n\"11\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    if nums[i]+nums[j] == target:\n",
    "                        res +=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len(nums)\n",
    "        num = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    num += 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(0, n-1):\n",
    "            for j in range(i+1, n):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    ans += 1\n",
    "                if nums[j] + nums[i] == target:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if nums[i] + nums[j] == target and j != i:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        return sum(''.join(l) == target for l in permutations(nums, 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j: continue\n",
    "                ret += nums[i] + nums[j] == target\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        return sum(1 for x, y in permutations(nums, 2) if x + y == target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    if nums[i]+nums[j]==target:\n",
    "                        res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        res = 0\n",
    "        table = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            table[num] += 1\n",
    "\n",
    "        for num in table:\n",
    "            size = len(num)\n",
    "            prefix, suffix = target[ :size], target[size: ]\n",
    "            if num == prefix and suffix in table:\n",
    "                if num == suffix:\n",
    "                    res += table[prefix] * (table[suffix] - 1)\n",
    "                else:\n",
    "                    res += table[prefix] * table[suffix]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if nums[i]+nums[j]==target and i!=j:\n",
    "                    # print(i,j)\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len ( nums )\n",
    "        res = 0\n",
    "        for i in range ( n ) :\n",
    "            for j in range ( n ) :\n",
    "                if i != j :\n",
    "                    if nums [ i ] + nums [ j ] == target :\n",
    "                        res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        ans = 0\n",
    "        m = defaultdict(int)\n",
    "        for s in nums:\n",
    "            n = len(s)\n",
    "            if len(target) < n:\n",
    "                continue\n",
    "            if  target[:n] == s:\n",
    "                ans += m[target[n:]]\n",
    "            if target[-n:] == s:\n",
    "                ans += m[target[:-n]]\n",
    "            m[s] += 1\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        from collections import Counter\n",
    "        cnt = Counter(nums)\n",
    "        n = len(target)\n",
    "        if n < 2: return 0\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            a = target[:i]\n",
    "            b = target[i:]\n",
    "            if a != b:\n",
    "                res += cnt[a] * cnt[b]\n",
    "            else:\n",
    "                res += cnt[a] * (cnt[b] - 1)\n",
    "        return res            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        count = 0\n",
    "        for key1 , value1 in enumerate(nums):\n",
    "            for key2 ,value2 in enumerate(nums):\n",
    "                if key1==key2:\n",
    "                    continue\n",
    "                elif  value1+value2==target:\n",
    "                    count+=1\n",
    "      \n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        res=0\n",
    "        table={}\n",
    "        for num in nums:\n",
    "            if num not in table:\n",
    "                table[num]=1\n",
    "            else:\n",
    "                table[num]+=1\n",
    "        for num in table:\n",
    "            size=len(num)\n",
    "            pre,suf=target[:size],target[size:]\n",
    "            if num==pre and suf in table:\n",
    "                if num==suf:\n",
    "                    res+=table[pre]*(table[suf]-1)\n",
    "                else:\n",
    "                    res+=table[pre]*table[suf]\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n=len(nums)\n",
    "        count=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if nums[i]+nums[j]==target and i!=j:\n",
    "                    count+=1\n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    ans += 1\n",
    "                if nums[j] + nums[i] == target:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for x, y in permutations(nums, 2):\n",
    "            if x + y == target:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\r\n",
    "        ans = 0\r\n",
    "        for i in range(len(nums)):\r\n",
    "            for j in range(len(nums)):\r\n",
    "                if i != j and nums[i] + nums[j] == target:\r\n",
    "                    ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    res += 1\n",
    "                if nums[j] + nums[i] == target:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        return sum(x + y == target for x, y in permutations(nums, 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len ( nums )\n",
    "        res = 0\n",
    "        for i in range ( n ) :\n",
    "            for j in range ( n ) :\n",
    "                if i != j :\n",
    "                    if nums [ i ] + nums [ j ] == target :\n",
    "                        res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        ans = 0\n",
    "        for x in range(len(nums)):\n",
    "            for y in range(len(nums)):\n",
    "                if x == y:\n",
    "                    continue\n",
    "                if nums[x] + nums[y] == target:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                \n",
    "                if nums[i] + nums[j] == target:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        return sum(x + y == target for x, y in permutations(nums, 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if nums[i] + nums[j] == target and i != j:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        num_map = Counter(nums)\n",
    "\n",
    "        res = 0 \n",
    "        for k, v in num_map.items(): \n",
    "            if target.startswith(k): \n",
    "                suffix = target[len(k):]\n",
    "                res += (v - (k == suffix)) * num_map[suffix]\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums, target: str) -> int:\n",
    "        num_map = Counter(nums)\n",
    "\n",
    "        res = 0\n",
    "        for k, v in num_map.items():\n",
    "            if target.startswith(k):\n",
    "                suffix = target[len(k):]\n",
    "                res += v * num_map[suffix]\n",
    "\n",
    "                if k == suffix:\n",
    "                    res -= num_map[suffix]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(0, len(nums)):\n",
    "                if i != j and nums[i] + nums[j] == target:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        ret = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(0,i):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    ret += 1\n",
    "            for k in range(i + 1, len(nums)):\n",
    "                if nums[i] + nums[k] == target:\n",
    "                    ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        if target and len(target) % 2 == 0 and target[:len(target) // 2] == target[-len(target) // 2:]:\n",
    "            special = target[:len(target) // 2] \n",
    "        else:\n",
    "            special = None\n",
    "        res = 0\n",
    "        special_num = 0\n",
    "        valid_str_l = {}\n",
    "        valid_str_r = {}\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if len(nums[i]) >= len(target):\n",
    "                continue\n",
    "            if nums[i] == target[:len(nums[i])]:\n",
    "                if len(nums[i]) not in valid_str_l:\n",
    "                    valid_str_l[len(nums[i])] = 1\n",
    "                else:\n",
    "                    valid_str_l[len(nums[i])] += 1\n",
    "                if special and len(nums[i]) == len(special) and nums[i] == special:\n",
    "                    special_num += 1\n",
    "\n",
    "            if nums[i] == target[-len(nums[i]):]:\n",
    "                if len(nums[i]) not in valid_str_r:\n",
    "                    valid_str_r[len(nums[i])] = 1\n",
    "                else:\n",
    "                    valid_str_r[len(nums[i])] += 1\n",
    "        \n",
    "        print(valid_str_l)\n",
    "        print(valid_str_r)\n",
    "        for i in valid_str_l:\n",
    "            if len(target) - i in valid_str_r:\n",
    "                if special and i == len(target) // 2:\n",
    "                    res += valid_str_l[i] * (valid_str_r[len(target) - i] - 1)\n",
    "                else:\n",
    "                    res += valid_str_l[i] * valid_str_r[len(target) - i]\n",
    "        \n",
    "        return int(res)\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        mapping = {}\n",
    "        for num in nums:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] += 1\n",
    "        result = 0\n",
    "        digits = list(mapping.keys())\n",
    "        for i in range(len(digits)):\n",
    "            for j in range(len(digits)):\n",
    "                if(i == j):\n",
    "                    continue\n",
    "                if(digits[i] + digits[j] == target):\n",
    "                    result += mapping[digits[i]]*mapping[digits[j]]\n",
    "        for d in digits:\n",
    "            if(d+d == target):\n",
    "                result += mapping[d]*(mapping[d]-1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        dic = Counter()\n",
    "        for s in nums:\n",
    "            if s == target[:len(s)]:\n",
    "                dic[target[len(s):]] += 1\n",
    "        \n",
    "        n = len(target)\n",
    "        if n % 2 == 0 and target[:n//2] == target[n//2:]:\n",
    "            if target[:n//2] in dic:\n",
    "                dic[target[:n//2]] -= 1\n",
    "        return sum(dic[x] for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        return sum(1 for x, y in permutations(nums, 2) if x + y == target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        i, n = 1, len(target)\n",
    "        while i < n:\n",
    "            p = \"\".join(target[:i])\n",
    "            s = \"\".join(target[i:])\n",
    "            print(p, s)\n",
    "            if p != s:\n",
    "                ans += cnt[p] * cnt[s]\n",
    "            else:\n",
    "                ans += cnt[p] * (cnt[p] - 1)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        count = 0\n",
    "        for i, item in enumerate(nums):\n",
    "            for j, sub_item in enumerate(nums):\n",
    "                if item + sub_item == target and i != j:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        l = nums.__len__()\n",
    "        ans = 0\n",
    "        for i in range(l):\n",
    "            for j in range(i+1, l):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    ans += 1\n",
    "                if nums[j] + nums[i] == target:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        c=0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]+nums[j]==target:\n",
    "                    c+=1\n",
    "                if nums[j]+nums[i]==target:\n",
    "                    c+=1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        special = None\n",
    "        if target and len(target) % 2 == 0 and target[:len(target) // 2] == target[-len(target) // 2:]:\n",
    "            special = True\n",
    "        res = 0\n",
    "        valid_str_l = {}\n",
    "        valid_str_r = {}\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if len(nums[i]) >= len(target):\n",
    "                continue\n",
    "            if nums[i] == target[:len(nums[i])]:\n",
    "                if len(nums[i]) not in valid_str_l:\n",
    "                    valid_str_l[len(nums[i])] = 1\n",
    "                else:\n",
    "                    valid_str_l[len(nums[i])] += 1\n",
    "\n",
    "            if nums[i] == target[-len(nums[i]):]:\n",
    "                if len(nums[i]) not in valid_str_r:\n",
    "                    valid_str_r[len(nums[i])] = 1\n",
    "                else:\n",
    "                    valid_str_r[len(nums[i])] += 1\n",
    "        \n",
    "        for i in valid_str_l:\n",
    "            if len(target) - i in valid_str_r:\n",
    "                if special and i == len(target) // 2:\n",
    "                    res += valid_str_l[i] * (valid_str_r[len(target) - i] - 1)\n",
    "                else:\n",
    "                    res += valid_str_l[i] * valid_str_r[len(target) - i]\n",
    "        \n",
    "        return int(res)\n",
    "            \n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        cnts = collections.Counter(nums)\n",
    "        ans = 0\n",
    "        for i in range(len(target) - 1):\n",
    "            pre = target[:i + 1]\n",
    "            suf = target[i + 1:]\n",
    "\n",
    "            if pre != suf:\n",
    "                ans += cnts[pre] * cnts[suf]\n",
    "            else:\n",
    "                ans += cnts[pre] * (cnts[pre] - 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        for x in nums: cnt[x] += 1\n",
    "        for x in cnt:\n",
    "            if x + x == target: ans += cnt[x] * (cnt[x] - 1)\n",
    "            for y in cnt:\n",
    "                if x == y: continue\n",
    "                if x + y == target: ans += cnt[x] * cnt[y]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n, count_l = len(target), Counter(nums)\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            res += count_l[target[:i]] * count_l[target[i:]]\n",
    "        if n % 2 == 0 and target[: n // 2] == target[n // 2:]:\n",
    "            res -= count_l[target[: n // 2]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and nums[i] + nums[j] == target:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j: continue\n",
    "                if nums[i] + nums[j] == target: ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for s in nums[:i] + nums[i+1:]:\n",
    "                if (nums[i] + s == target):\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        cnt=Counter(nums)\n",
    "        ans=0\n",
    "        for x in cnt:\n",
    "            if x+x==target:\n",
    "                ans+=cnt[x]*(cnt[x]-1)\n",
    "            else:\n",
    "                m=len(x)\n",
    "                if target[:m]==x:\n",
    "                    ans+=cnt[x]*cnt[target[m:]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        res = 0\n",
    "        ct = Counter()\n",
    "        n = len(target)\n",
    "        for num in nums:\n",
    "            ct[num] += 1\n",
    "        for i in range(n):\n",
    "            a = target[0:i + 1]\n",
    "            b = target[i + 1:]\n",
    "            if a in ct and b in ct:\n",
    "                if a == b:\n",
    "                    res += ct[a] * (ct[b] - 1)\n",
    "                else:\n",
    "                    res += ct[a] * ct[b]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(nums)):\n",
    "                if i != j and nums[i] + nums[j] == target:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        a=0     \n",
    "        for i in range(len(nums)):\n",
    "            for j in range(1+i,len(nums)):\n",
    "                if nums[i]+nums[j]==target:\n",
    "                    a+=1\n",
    "                if nums[j]+nums[i]==target:\n",
    "                    a+=1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numOfPairs(self, nums: List[str], target: str) -> int:\n",
    "        fh = 0\n",
    "        n = len(target)\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if len(nums[i]) + len(nums[j]) == n:\n",
    "                    if nums[i][0] == target[0] and nums[j][-1] == target[-1] and nums[i]+nums[j] == target:\n",
    "                        fh += 1\n",
    "                    if nums[j][0] == target[0] and nums[i][-1] == target[-1] and nums[j]+nums[i] == target:\n",
    "                        fh += 1\n",
    "        return fh\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
